package com.sicheng.lc.周赛.分类.dp.数位;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/19 8:55
 */
public class _网易真题_n以内包含25的数的个数 {
    // 和x 出现的套路一样 转换成求 ______xy_____ xy在每一个位置的贡献值 todo

    int dgt(int x) {
        int cnt = 0;
        while (x != 0) {
            x /= 10;
            cnt++;
        }
        return cnt;
    }

    static int[] pow = new int[10];

    static {
        pow[0] = 1;
        for (int i = 1; i < pow.length; i++) {
            pow[i] = pow[i - 1] * 10;
        }
    }

    //数位dp的第一道模板题

    long f(int n, int x, int y) {
        if (n < x * 10 + y)
            return 0;
        int cnt = dgt(n);
        int k = x * 10 + y;
        long res = 0;
        for (int i = 2; i <= cnt; i++) {
            int p = pow[i - 2], l = n / p / 100, r = n % p, dj = n / p % 100;
            if (k >= 10) {
                res += (long) l * p;
            } else if (l > 0) {
                res += (long) (l - 1) * p;
            }
            if (dj == k && (k >= 10 || l > 0)) {
                res += r + 1;
            }
            if (dj > k && (k >= 10 || l > 0)) {
                res += p;
            }
        }

        return res;

    }

}
